Common Subexpression Elimination in a Lazy Functional Language”, Lehrstuhl f¨ur

Abstract. Common subexpression elimination is a well-known compiler optimisation that saves time by avoiding the repetition of the same com-putation. To our knowledge it has not yet been applied to lazy functional programming languages, although there are several advantages. First, the referential transparency of these languages makes the identification of com-mon subexpressions very simple. Second, more common subexpressions can be recognised because they can be of arbitrary type whereas standard com-mon subexpression elimination only shares primitive values. However, be-cause lazy functional languages decouple program structure from data space allocation and control flow, analysing its effects and deciding under which conditions the elimination of a common subexpression is beneficial proves to be quite difficult. We developed and implemented the transformation for the language Haskell by extending the Glasgow Haskell compiler and measured its effectiveness on real-world programs. 1 Transformation of Different Language Classe